#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// dfs 方法
vector<bool> vi;
vector<bool> onPath;
bool hasCycle = 0;
void dfs(int x, const vector<vector<int>>& graph) {
    if (onPath[x]) hasCycle = 1;
    if (hasCycle || vi[x]) return;
    vi[x] = 1;
    onPath[x] = 1;
    for (int neighbour : graph[x]) { dfs(neighbour, graph); }
    onPath[x] = 0;
}

bool graphHasCycle(vector<vector<int>>& graph) {
    int n = graph.size();
    vi.resize(n, 0);
    onPath.resize(n, 0);
    for (int i = 0; i < n; i++) {
        if (!vi[i]) dfs(i, graph);
    }
    return hasCycle;
}

// 拓扑序列方法
bool graphHasCycle(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> indegree(n, 0);
    for (int i = 0; i < n; i++) {
        for (int neighbour : graph[i]) indegree[neighbour]++;
    }
    
    queue<int> Q;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
            cnt++;
        }
    }

    while (!Q.empty()) {
        int fr = Q.front();
        Q.pop();
        for (int neighbour : graph[fr]) {
            --indegree[neighbour];
            if (indegree[neighbour] == 0) {
                Q.push(neighbour);
                cnt++;
            }
        }
    }

    if (cnt == n) return 0;
    return 1;
}
